In a packet-based transmission system, a large number of timers are frequently used in networking protocol processing and protocol termination applications purposes. One example is the retransmission timer of the transmission control protocol (TCP) or of the stream control transmission protocol (SCTP). Therein, an element or a packet will be retransmitted when no acknowledgement for a receiving of a particular packet has been received within the specified timeout interval (RTO). Thus, for each of the data packets being transmitted a dedicated timeout interval (RTO) is assigned. The timeout interval depends on the connection and link characteristics and can vary between multiple 10 milliseconds up to several tens of seconds. When the timeout interval for a packet has expired, a timeout event occurs wherein a special handling is invoked.
The handling of the timeout intervals of each transmitted packet is conventionally handled by software. The software finds the appropriate packet and connection to do the retransmission. To each of the packets being transmitted, one timer is associated.
Such software basically performs three basic operations. When a packet is transmitted for the first time, a timer is initialized with the timeout interval. The timer is normally realized by a memory position wherein a value is stored which represents the timeout interval. The value stored is relative to a time base wherein the difference between the time base value and the timeout interval stored corresponds to the timer value. When the acknowledgement for this packet is received before the timeout interval has passed, the timer is cleared. The timer can now be used for a different packet that has no further association with the before transmitted packet. If the timeout interval expires before an acknowledgement of receipt has been received, the software invokes a special handling regarding the respective data packet e.g. in order to retransmit the packet or react otherwise, e.g. by reporting an error. The same timer can be used for the re-transmission but it is reinitialized with the same or a different timeout interval.
Today almost all network protocol implementations use software solutions to manage the timers, but with increasing numbers of timers to be managed by software, the excess delay grows almost exponentially. Software timer management is for example disclosed in the document “Hashed Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility”, by George Varghese, Anthony Lauck, IEEE/ACM Transactions on Networking, 1997.
Another known solution is to delegate the timing function of the timer manager from software timer to hardware timers into a so-called co-processor including a number of hardware-implemented timers. This is disclosed in the document “A Hardware/Software Codesign Strategy for the Implementation of High-Speed Protocols” by Marco Heddes, Technical University Eindhoven, 1995. Hardware co-processors are less flexible than the software solution. The latency in such a design is large because of the number of external memory accesses.
In a software solution, timer values indicating timeout intervals for each of the transmitted packets are stored in a linked list wherein each member of the list has a reference to a succeeding and a following member of this list, except it is the first or last member of the list. The list is sorted from a minimum timeout interval to a maximum timeout interval wherein each new timer value to be added is included into the list as soon as the packet has been transmitted, and therefore the timer is set. The inclusion of the respective timer value to be set is time-consuming as the respective timer value is compared with the timer values present in the linked list. The position of the timer value to be inserted is defined such that the preceding element of the link list represents a smaller timer value and wherein the following element of the link list represents a timer value which is higher than the timer value to be inserted or vice versa. This method is time-consuming.